﻿using System.Collections.Generic;
using System.IO;

namespace System
{
	public delegate double DijkstraDistance<TP>(DijkstraPoint<TP> P1, DijkstraPoint<TP> P2);
	public delegate void DijkstraPointEvent<TP>(DijkstraPoint<TP> p);

	public enum DijkstraFlag : byte
	{
		Processed,
		Active,
		None
	}

	public class DijkstraEdge<TP> : GraphEdge<double, TP>
	{
		public new DijkstraPoint<TP> ThisEnd;
		public new DijkstraPoint<TP> FarEnd;
		public DijkstraEdge(DijkstraPoint<TP> p1, DijkstraPoint<TP> p2, DijkstraDistance<TP> d)
			: base(p1, p2, -1)
		{
			Content = d(p1, p2);
		}
		public DijkstraEdge(DijkstraPoint<TP> p1, DijkstraPoint<TP> p2, double d)
			: base(p1, p2, d)
		{
		}
	}
	public class DijkstraPoint<TP> : GraphPoint<TP, double>
	{
		public int Dij_Group = 0;
		public int Dij_Size = 0;
		public double Dij_Dist;
		public DijkstraFlag Dij_Status;
		public DijkstraPoint<TP> Dij_Parent;
		public DijkstraPoint<TP> Dij_Root;
		public DijkstraPoint(TP content)
			: base(content)
		{
		}

		public DijkstraPoint(int gr, String S)
			: base(S)
		{
			Dij_Group = gr;
		}

		public void Dij_Reset()
		{
			Dij_Dist = -1;
			Dij_Size = 0;
			Dij_Status = DijkstraFlag.None;
			Dij_Parent = null;
			Dij_Root = null;
		}
		public void Dij_SetFirst()
		{
			Dij_Dist = 0;
			Dij_Status = DijkstraFlag.Active;
			Dij_Parent = null;
			Dij_Root = this;
		}

		public bool Dij_Process(DijkstraPointEvent<TP> e)
		{
			bool Res = false;
			if (Dij_Status == DijkstraFlag.Active)
			{/*
				foreach (var X in Adjacents)
				{
					if (X.Key.Dij_Dist == -1 || Dij_Dist + X.Value < X.Key.Dij_Dist)
					{
						X.Key.Dij_Status = DijkstraFlag.Active;
						X.Key.Dij_Dist = Dij_Dist + X.Value;
						X.Key.Dij_Parent = this;
						X.Key.Dij_Root = Dij_Root;
						Res = true;
					}
				}*/
				Dij_Status = DijkstraFlag.Processed;
			}
			return Res;
		}

		public static double V3DDist(DijkstraPoint<V3D> p1, DijkstraPoint<V3D> p2)
		{
			return (p1.Content - p2.Content).Length;
		}

		public virtual void Load(TextReader R)
		{
			Dij_Group = int.Parse(R.ReadLine());
			R.ReadLine();
		}

		/*public DijkstraEdge<TP> Bind(DijkstraPoint<TP> p, DijkstraPoint<TP> a, double content)
		{
			DijkstraEdge<TP> E = (DijkstraEdge<TP>)Edges.Find(x => (x.ThisEnd == p && x.FarEnd == a));
			if (E != null)
				E.Content = content;
			else
				Edges.Add(E = p.Bind(a, content));
			return E;
		}
		public DijkstraEdge<TP> Bind(DijkstraPoint<TP> p, double d)
		{
			var X = FindEdges(x => x.FarEnd == p) as DijkstraEdge<TP>[];
			if (X == null)
			{
				var newedge = new DijkstraEdge<TP>(this, p, d);
				Edges.Add(newedge);
				return newedge;
			}
			else
				X[0].Content = d;
			return X[0];
		}
		public void _Bind(DijkstraEdge<TP> edge)
		{
			if (edge.ThisEnd != this)
				throw new Exception("Start point mismatch");
			var X = FindEdges(x => x.FarEnd == edge.FarEnd);
			if (X.Count > 0)
				throw new Exception("Edge duplication error");
			Edges.Add(edge);
		}*/
	}
	public partial class DijkstraGraph<TP> : Graph<TP, double>
	{
		public new DijkstraPoint<TP> AddPoint(TP content)
		{
			DijkstraPoint<TP> Res = new DijkstraPoint<TP>(content);
			Points.Add(Res);
			Res.ID = Points.Count;
			return Res;
		}
		public List<KeyValuePair<int, DijkstraPoint<TP>>> Areas = new List<KeyValuePair<int, DijkstraPoint<TP>>>();
		public Dictionary<int, DijkstraPoint<TP>> MaxAreas = new Dictionary<int, DijkstraPoint<TP>>();
		//Calculate consecutive areas
		public void CalculateAreas()
		{
			TimerLog T = new TimerLog();
			T.Start();
			Areas.Clear();
			foreach (DijkstraPoint<TP> p in Points)
				p.Dij_Reset();
			//T.Log("Reset points");
			DijkstraPoint<TP> Current_Group = Points[0] as DijkstraPoint<TP>;
			Current_Group.Dij_Root = Current_Group;

			while (Current_Group != null)
			{
				//Start from current
				List<DijkstraPoint<TP>> Nexts = new List<DijkstraPoint<TP>>();
				//LinkedList<GraphPoint<T>> Nexts = new LinkedList<GraphPoint<T>>();

				Nexts.Add(Current_Group);
				//Iterate through same group
				while (Nexts.Count > 0)
				{
					var Current = Nexts[0];
					Nexts.RemoveAt(0);
					Current.Dij_Root.Dij_Size++;
					Current.Dij_Status = DijkstraFlag.Processed;

					/**foreach (var adj in Current.Adjacents)
						if (adj.Key.Dij_Group == Current.Dij_Group && adj.Key.Dij_Status != DijkstraFlag.Processed && !Nexts.Contains(adj.Key))
						{
							adj.Key.Dij_Root = Current.Dij_Root;
							adj.Key.Dij_Parent = Current;
							Nexts.Add(adj.Key);
						}*/
				}
				Areas.Add(new KeyValuePair<int, DijkstraPoint<TP>>(Current_Group.Dij_Group, Current_Group));

				Current_Group = null;

				for (int i = 0; Current_Group == null && i < Points.Count; i++)
					if ((Points[i] as DijkstraPoint<TP>).Dij_Status != DijkstraFlag.Processed)
					{
						Current_Group = Points[i] as DijkstraPoint<TP>;
						Current_Group.Dij_Root = Current_Group;
					}
			}
			//T.Log("Set points roots");
			//Collect maximum areas with a representing member
			foreach (DijkstraPoint<TP> P in Points)
				if (P.Dij_Root != P)
					P.Dij_Size = P.Dij_Root.Dij_Size;
			//T.Log("Set sizes");
			MaxAreas.Clear();
			foreach (var a in Areas)
				if (MaxAreas.ContainsKey(a.Key) && MaxAreas[a.Key].Dij_Size < a.Value.Dij_Size)
					MaxAreas[a.Key] = a.Value;
				else if (!MaxAreas.ContainsKey(a.Key))
					MaxAreas.Add(a.Key, a.Value);
			//T.Log("max area set");
		}

		public void Bind(DijkstraPoint<TP> p, DijkstraDistance<TP> Distance, params DijkstraPoint<TP>[] neighbors)
		{
			Array.ForEach(neighbors, n =>
			{
				DijkstraEdge<TP> E = Edges.Find(x => (x.ThisEnd == p && x.FarEnd == n)) as DijkstraEdge<TP>;
				if (E != null)
					E.Content = Distance(p, n);
				else
				{
					var e = new DijkstraEdge<TP>(p, n, Distance);
					Bind(e);
				}
			});
		}

		public void Search(params DijkstraPoint<TP>[] starts)
		{
			foreach (DijkstraPoint<TP> p in Points)
				p.Dij_Reset();
			foreach (DijkstraPoint<TP> p in starts)
				p.Dij_SetFirst();

			List<DijkstraPoint<TP>> nexts = new List<DijkstraPoint<TP>>();
			nexts.AddRange(starts);
			while (nexts.Count > 0)
			{
				DijkstraPoint<TP> current = nexts[0];
				nexts.RemoveAt(0);
				foreach (var E in current.Edges)
				{
					var p1 = E.ThisEnd;
					var p2 = E.FarEnd;
					DijkstraPoint<TP> next = p2 as DijkstraPoint<TP>;
					double d = current.Dij_Dist + E.Content;
					if (next.Dij_Status == DijkstraFlag.None || d < next.Dij_Dist)
					{
						nexts.Add(next);
						next.Dij_Dist = d;
						next.Dij_Root = current.Dij_Root;
						next.Dij_Parent = current;
						next.Dij_Status = DijkstraFlag.Active;
					}
				}
				current.Dij_Status = DijkstraFlag.Processed;
			}
		}
	}
	public static class DijExt
	{
		public static void Bind3D(this DijkstraGraph<V3D> graph, DijkstraPoint<V3D> p1, params DijkstraPoint<V3D>[] p2)
		{
			DijkstraDistance<V3D> eq = V3DDistance;
			graph.Bind(p1, (x1, x2) =>
			{
				return (x1.Content - x2.Content).Length;
			}, p2);
		}
		public static double V3DDistance(DijkstraPoint<V3D> p1, DijkstraPoint<V3D> p2)
		{
			return (p1.Content - p2.Content).Length;
		}
	}
	/*
	public class Dij3D : DijkstraGraph<V3D>
	{
		public void Bind(DijkstraPoint<V3D> p1, DijkstraPoint<V3D> p2)
		{
			DijkstraDistance<V3D> eq = V3DDistance;
			Bind(p1, (x1, x2) =>
			{
				return (x1.Content - x2.Content).Length;
			}, p2);
		}
		public static double V3DDistance(DijkstraPoint<V3D> p1, DijkstraPoint<V3D> p2)
		{
			return (p1.Content - p2.Content).Length;
		}
	}*/
}